package demo.practice.dp;

public class P1259_2 {
    public static void main(String[] args) {
        P1259_2 p1259_2= new P1259_2();
        int res=  p1259_2.res(new int[]{13 ,7 ,9, 16 ,38, 24 ,37, 18, 44, 19 ,21 ,22, 63, 15});
        System.out.println(res);
    }
    public int res(int[] t) {
        if (t == null || t.length == 0)
            return 0;
        int w = t.length;
        int dp[] = new int[t.length];
        /*for (int i = 0; i < w; i++) {
            dp[i] = 1;
        }*/

        for (int i = 0; i < w; i++) {
            dp[i] = 1;
            //int max=dp[i];
            for(int j=i-1;j>=0;j--){
                if(t[i] >= t[j]){
                    //if(max<dp[j]+1){max= dp[j]+1};
                    dp[i]=Math.max(dp[i],dp[j]+1) ;
                }
            }
            //dp[i]= max;
        }

        int res=1;
        for (int i = 0; i < w; i++) {
            res= Math.max(res,dp[i]);
        }
        return res;
    }
}


